Article 4112

Title of the article

UNRELIABILITY LOWER-BOUND ESTIMATE OF NONBRANCHING PROGRAMMES
WITH A CONDITIONAL STOP OPERATOR

Authors

Alekhina Marina Anatolyevna, Doctor of physical and mathematical sciences, professor, head of sub-department of discrete mathematics, Penza State University, dm@pnzgu.ru
Grabovskaya Svetlana Mikhaylovna, Senior lecturer, sub-department of discrete mathematics, Penza State University, swetazin@mail.ru

Index UDK

519.718

Abstract

The article considers a problem of synthesis of nobranching programs with conditional stop-operator. All functional operators are supposed to be subject to out-put inverse failures with probability  ε (ε(0,1/2). Conditional stop-operators are absolutely reliable. Any boolean function fK (class K is found explicitly) is proved to be impossible to realize by irreducible nobranching program with unreliability of less than ε(1 – ε)m, where m – the number of functional operators in the program. These and the previous results on the upper bound for the unreliability of the nobranching programs prove that almost all functions can be realized by asymptotically optimal reliable nobranching programs that operate with unreliability asymptotically equal to ε at ε → 0.

Key words

boolean functions, nobranching programs, conditional stop-operator, synthesis, reliability

Download PDF

 

Дата создания: 17.07.2014 07:07
Дата обновления: 22.07.2014 11:40